package 剑指II;

import 链表.ListNode;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-06
 **/

public class Jz021删除链表的倒数第n个结点 {

    /**
     * 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * <p>
     * 示例 1：
     * 输入：head = [1,2,3,4,5], n = 2
     * 输出：[1,2,3,5]
     * 示例 2：
     * 输入：head = [1], n = 1
     * 输出：[]
     * 示例 3：
     * 输入：head = [1,2], n = 1
     * 输出：[1]
     * <p>
     * 提示：
     * 链表中结点的数目为 sz
     * 1 <= sz <= 30
     * 0 <= Node.val <= 100
     * 1 <= n <= sz
     * <p>
     * 进阶：能尝试使用一趟扫描实现吗？
     */

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode slow = head;
        ListNode fast = head;
        ListNode last = head;

        while (n > 0) {
            fast = fast.next;
            n--;
        }

        if (fast == null) {
            head = head.next;
            slow.next = null;
            return head;
        }

        while (fast != null) {
            fast = fast.next;
            last = slow;
            slow = slow.next;
        }

        last.next = slow.next;
        slow.next = null;


        return head;
    }

    public static void main(String[] args) {
        ListNode listNode = ListNode.createListNode(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11});
        Jz021删除链表的倒数第n个结点 n = new Jz021删除链表的倒数第n个结点();
        ListNode result = n.removeNthFromEnd(listNode, 11);
        ListNode.printListNode(result);
    }

}
